import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;
import java.util.Map;


public class ShortestWeightedPath {

	static Map<Vetex, Integer> map = new HashMap<Vetex, Integer>();
	
	public static void main(String[] args){
		
	}
	
	public static int shortestPath(Vetex src, Vetex dst){
		int min = 10000;
		
		for(int i=0;i<dst.edges.size();i++){
			Vetex v = dst.edges.get(i).v1;
			if(v == dst){
				v = dst.edges.get(i).v2;
			}
			
			if(v==src){
				map.put(v, dst.edges.get(i).weight);
				return dst.edges.get(i).weight;
			}
			else{
				int candidate =0;
				if(map.containsKey(v)){
					candidate = map.get(v).intValue();
				}
				else{
					candidate = shortestPath(src, v);
					//map.put(v,candidate);
				}
				min = min<candidate+dst.edges.get(i).weight?min:candidate+dst.edges.get(i).weight;
			}
		}
		map.put(dst, min);
		return min;
	}
}
class Vetex{
	public int id;
	List<Edge> edges = new ArrayList<Edge>();
}

class Edge{
	public int weight;
	public Vetex v1;
	public Vetex v2;
}